package com.wm.algorithm.binarytree;

import com.wm.algorithm.linked.entity.ListNode;

import java.util.*;

/**
 * @ClassName: MediumBinaryTree
 * @Description: 中等级二叉树
 * @Author: Deamer
 * @Date: 2022/6/7 23:17
 **/
public class MediumBinaryTree {

    public static void main(String[] args) {
        MapSum mapSum = new MapSum();
        mapSum.insert("apple", 3);
        mapSum.sum("ap");
        mapSum.insert("app", 2);
        mapSum.sum("ap");
    }

    /**
     * 147. 对链表进行插入排序
     * https://leetcode.cn/problems/insertion-sort-list/description/
     * 方法：从前往后找插入点+迭代
     * 思路：遍历链表，定义一个lastSorted表示前面排好序的链表的最后一个节点，prev节点表示
     * 需要插入的元素位置的前一个节点。通过比较lastSorted的值和cur的值大小，判断cur需要插入的位置，
     * 如果前者大，那么需要从头遍历，将cur插入到pre的后面，如果后者大，直接更新lastSorted即可。
     * cur变为lastSorted的下一个节点。
     *
     * @param head
     * @return
     */
    // O(n^2)/O(1)
    public ListNode insertionSortList(ListNode head) {
        // 首先判断给定的链表是否为空，若为空，则不需要进行排序，直接返回。
        if (head == null) {
            return null;
        }
        // 创建哑节点 dummyHead，令 dummyHead.next = head。引入哑节点是为了便于在 head 节点之前插入节点。
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        // 维护 lastSorted 为链表的已排序部分的最后一个节点，初始时 lastSorted = head。
        // 维护 cur 为待插入的元素，初始时 cur = head.next。
        ListNode lastSorted = head, cur = head.next;
        while (cur != null) {
            if (lastSorted.val <= cur.val) {
                // cur 应该位于 lastSorted 之后，将 lastSorted 后移一位，cur 变成新的 lastSorted。
                lastSorted = lastSorted.next;
            } else {
                // 链表的头节点开始往后遍历链表中的节点，寻找插入 cur 的位置。令 prev 为插入 cur 的位置的前一个节点
                ListNode prev = dummyHead;
                while (prev.next.val <= cur.val) {
                    prev = prev.next;
                }
                // cur节点插入到prev节点后面
                lastSorted.next = cur.next;
                // 之前的prev下一个节点放在插入节点后面
                cur.next = prev.next;
                // 插入节点为prev的下一个节点
                prev.next = cur;
            }
            // 更新cur节点，变更为下一个待插入的节点
            cur = lastSorted.next;
        }
        return dummyHead.next;
    }

    /**
     * LCR 153. 二叉树中和为目标值的路径
     * https://leetcode.cn/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/
     * 方法：递归+前序位置
     * 思路：在前序位置将节点值加入到集合中，使用目标值减去当前的节点值，判断目标值是否为0以及左右子节点是否是叶子节点，
     * 如果是表示找到了一个路径，没有的话就递归在左右子节点中查找。在后序位置不要忘记做剪枝的操作。
     *
     * @param root
     * @param target
     * @return
     */
    // O(N)/O(N)
    List<List<Integer>> res3 = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> pathTarget(TreeNode root, int target) {
        traversePath(root, target);
        return res3;
    }

    private void traversePath(TreeNode root, int target) {
        if (root == null) {
            return;
        }
        path.add(root.val);
        target -= root.val;
        // 一直到根节点
        if (target == 0 && root.left == null && root.right == null) {
            res3.add(new LinkedList<>(path));
        }

        traversePath(root.left, target);
        traversePath(root.right, target);
        path.removeLast();
    }

    /**
     * 337. 打家劫舍 III
     * 方法：动态规划+二叉树的后序位置
     * 思路：递归方法dp定位为arr[0]表示不抢根节点得到的最大钱数，arr[1]表示抢根节点获得的最大钱数。
     * 这里利用二叉树的节点的后序位置去更新抢或不抢获取的受益
     *
     * @param root
     * @return
     */
    //O(n)/O(n:堆栈所需要的空间大小)
    public int rob(TreeNode root) {
        int[] res = dp6(root);
        return Math.max(res[0], res[1]);
    }

    /* 返回一个大小为 2 的数组 arr
        arr[0] 表示不抢 root 的话，得到的最大钱数
        arr[1] 表示抢 root 的话，得到的最大钱数 */
    private int[] dp6(TreeNode root) {
        if (root == null) {
            return new int[]{0, 0};
        }
        int[] left = dp6(root.left);
        int[] right = dp6(root.right);

        // 后序位置
        // 抢，下家就不能抢了
        int rob = root.val + left[0] + right[0];
        // 不抢，下家可抢可不抢，取决于收益大小
        int not_rob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return new int[]{not_rob, rob};
    }


    /**
     * 222. 完全二叉树的节点个数
     * https://leetcode.cn/problems/count-complete-tree-nodes/
     * 方法：满二叉树与普通二叉树计算节点数相结合
     * 思路：满二叉树是每层的节点都是满的，节点总数和树的高度有关系，此时计算节点数可根据等比求和来极计算：2^h-1（h为树的高度）;O(n)
     * 普通二叉树直接使用递归的形式计算，即根节点+左子树的节点数+右子树的节点数。O(logn)
     * 二者结合计算的目的是降低时间复杂度。先判断树的结构确定树的类型之后计算。
     *
     * @param root
     * @return
     */

    // O(logN * logN)/O(N)
    public int countNodes(TreeNode root) {
        TreeNode lNode = root, rNode = root;
        // 沿最左侧和最右侧分别计算高度
        int lh = 0, rh = 0;
        while (lNode != null) {
            lNode = lNode.left;
            lh++;
        }
        while (rNode != null) {
            rNode = rNode.right;
            rh++;
        }
        // 如果左右侧计算的高度相同，则是一棵满二叉树
        if (lh == rh) {
            return (int) Math.pow(2, lh) - 1;
        }
        // 如果左右侧的高度不同，则按照普通二叉树的逻辑计算
        return 1 + countNodes(root.left) + countNodes(root.right);
    }


    /**
     * 1650. 二叉树的最近公共祖先 III
     * 方法：两条单链表寻找交点+对称补齐
     *
     * @param p
     * @param q
     * @return
     */
    // O(n)/O(1)
    public Node2 lowestCommonAncestor(Node2 p, Node2 q) {
        // 施展链表双指针技巧
        Node2 a = p, b = q;
        while (a != b) {
            // a 走一步，如果走到根节点，转到 q 节点
            if (a == null) {
                a = q;
            } else {
                a = a.parent;
            }
            // b 走一步，如果走到根节点，转到 p 节点
            if (b == null) {
                b = p;
            } else {
                b = b.parent;
            }
        }
        return a;
    }

    private class Node2 {
        int val;
        Node2 left;
        Node2 right;
        Node2 parent;
    }

    /**
     * 235. 二叉搜索树的最近公共祖先
     * 方法2：迭代+BST左小右大性质
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    // O(n)/O(1)
    public TreeNode lowestCommonAncestor4(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode ancestor = root;
        while (true) {
            if (ancestor.val > p.val && ancestor.val > q.val) {
                ancestor = ancestor.left;
            } else if (ancestor.val < p.val && ancestor.val < q.val) {
                ancestor = ancestor.right;
            } else {
                break;
            }
        }
        return ancestor;
    }

    /**
     * 235. 二叉搜索树的最近公共祖先
     * 方法1：回溯+前序位置+BST左小右大性质
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    // O(n)/O(n)
    public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode p, TreeNode q) {
        // 先找到二者的最小值和最大值
        int minVal = Math.min(p.val, q.val);
        int maxVal = Math.max(p.val, q.val);
        return find3(root, minVal, maxVal);
    }

    // 在 BST 中寻找 minVal 和 maxVal 的最近公共祖先节点
    private TreeNode find3(TreeNode root, int minVal, int maxVal) {
        if (root == null) {
            return null;
        }
        if (root.val < minVal) {
            // 当前节点太小，去右子树找
            return find3(root.right, minVal, maxVal);
        }
        if (root.val > maxVal) {
            // 当前节点太大，去左子树找
            return find3(root.left, minVal, maxVal);
        }
        return root;
    }

    /**
     * 1644、二叉树的最近公共祖先II
     * 题目描述：p和q不一定存在于树中，所以你不能遇到一个目标值就直接返回，而应该对二叉树进行完全搜索（遍历每一个节点），如果发现p或q不存在于树中，那么是不存在LCA的。
     * 方法：回溯+后序位置
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    // O(n)/O(n)
    // 用于记录 p 和 q 是否存在于二叉树中
    boolean foundP = false, foundQ = false;

    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode lcaNode = find2(root, p.val, q.val);
        if (!foundP || !foundQ) {
            return null;
        }
        // p 和 q 都存在二叉树中，才有公共祖先
        return lcaNode;
    }

    // 在二叉树中寻找 val1 和 val2 的最近公共祖先节点
    private TreeNode find2(TreeNode root, int val1, int val2) {
        if (root == null) {
            return null;
        }
        TreeNode left = find2(root.left, val1, val2);
        TreeNode right = find2(root.right, val1, val2);

        // 后序位置，判断当前节点是不是 LCA 节点
        if (left != null && right != null) {
            return root;
        }

        // 后序位置，判断当前节点是不是目标值
        if (root.val == val1 || root.val == val2) {
            if (root.val == val1) {
                foundP = true;
            }
            if (root.val == val2) {
                foundQ = true;
            }
        }
        return left != null ? left : right;
    }

    /**
     * 1676、二叉树的最近公共祖先 IV
     * 题目描述：依然给你输入一棵不含重复值的二叉树，但这次不是给你输入p和q两个节点了，而是给你输入一个包含若干
     * 节点的列表nodes（这些节点都存在于二叉树中），让你算这些节点的最近公共祖先
     * 方法：回溯+前、后序位置
     *
     * @param root
     * @param nodes
     * @return
     */
    // O(n)/O(n)
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode[] nodes) {
        // 将列表转化成哈希集合，便于判断元素是否存在
        Set<Integer> nodeSet = new HashSet<>();
        for (TreeNode node : nodes) {
            nodeSet.add(node.val);
        }
        return find2(root, nodeSet);
    }

    // 在二叉树中寻找 values 的最近公共祖先节点
    private TreeNode find2(TreeNode root, Set<Integer> nodeSet) {
        if (root == null) {
            return null;
        }
        // 前序位置，判断LCA是否为当前节点
        if (nodeSet.contains(root.val)) {
            return root;
        }
        // 后序位置，已经知道左右子树是否存在目标值
        TreeNode left = find2(root, nodeSet);
        TreeNode right = find2(root, nodeSet);
        if (left != null && right != null) {
            // 当前节点是 LCA 节点
            return root;
        }
        return left != null ? left : right;
    }


    /**
     * 236. 二叉树的最近公共祖先
     * https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
     * 方法：回溯+前、后序位置
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    // O(n)/O(n)
    // 时间复杂度：O(n)，其中 n 是二叉树的节点数。二叉树的所有节点有且只会被访问一次，因此时间复杂度为O(n)。
    // 空间复杂度：O(n)，其中 n 是二叉树的节点数。递归调用的栈深度取决于二叉树的高度，二叉树最坏情况下为一条链，此时高度为n，因此空间复杂度为 O(n)。
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return find(root, p.val, q.val);
    }

    // 在二叉树中寻找 val1 和 val2 的最近公共祖先节点
    private TreeNode find(TreeNode root, int val1, int val2) {
        if (root == null) {
            return null;
        }
        // 前序位置
        if (root.val == val1 || root.val == val2) {
            // 如果遇到目标值，直接返回
            return root;
        }
        TreeNode left = find(root.left, val1, val2);
        TreeNode right = find(root.right, val1, val2);
        // 后序位置，已经知道左右子树是否存在目标值
        if (left != null && right != null) {
            // 当前节点是 LCA 节点
            return root;
        }
        return left == null ? right : left;
    }

    /**
     * 341. 扁平化嵌套列表迭代器
     * https://leetcode.cn/problems/flatten-nested-list-iterator/
     * 方法2：利用Trie的设计思想，惰性求值。将集合中有列表的全部打平，最终将全部结果值平铺保存于集合中。判断是否有值时，直接判断集合第一个元素是否存在集合。
     * 取出下一个值直接取集合第一个元素
     */
    class NestedIterator2 implements Iterator<Integer> {
        LinkedList<NestedInteger> list;

        // O(1)/O(n)
        public NestedIterator2(List<NestedInteger> nestedList) {
            // 不直接用 nestedList 的引用，是因为不能确定它的底层实现
            // 必须保证是 LinkedList，否则下面的 addFirst 会很低效
            this.list = new LinkedList<>(nestedList);
        }

        // 最好：O(1)；最坏O(m*n)/O(n)
        @Override
        public boolean hasNext() {
            // 循环拆分列表元素，直到列表第一个元素是整数类型
            while (!list.isEmpty() && !list.get(0).isInteger()) {
                // 当列表开头第一个元素是列表类型时，进入循环
                List<NestedInteger> oneList = list.remove(0).getList();
                // 将第一个列表打平并按顺序添加到开头
                for (int i = oneList.size() - 1; i >= 0; i--) {
                    list.addFirst(oneList.get(i));
                }
            }
            return !list.isEmpty();
        }

        // O(1)/O(n)
        @Override
        public Integer next() {
            // hasNext 方法保证了第一个元素一定是整数类型
            return list.remove(0).getInteger();
        }
    }

    /**
     * 341. 扁平化嵌套列表迭代器
     * https://leetcode.cn/problems/flatten-nested-list-iterator/
     * 方法1：利用Trie的设计思想，使用构造方法加载全部整数值存储到集合中
     */
    class NestedIterator implements Iterator<Integer> {

        Iterator<Integer> it;

        // O(n)/O(n)
        public NestedIterator(List<NestedInteger> nestedList) {
            // 存放将 nestedList 打平的结果
            List<Integer> res = new ArrayList<>();
            for (NestedInteger node : nestedList) {
                // 以每个节点为根遍历
                traverseInteger(node, res);
            }
            // 得到 result 列表的迭代器
            it = res.iterator();
        }

        // 遍历以 root 为根的多叉树，将叶子节点的值加入 res 列表
        private void traverseInteger(NestedInteger node, List<Integer> res) {
            if (node.isInteger()) {
                // 到达叶子节点
                res.add(node.getInteger());
                return;
            }
            // 遍历框架
            for (NestedInteger child : node.getList()) {
                traverseInteger(child, res);
            }
        }

        // O(1)/O(n)
        @Override
        public Integer next() {
            if (it == null) {
                return null;
            }
            return it.next();
        }

        // O(1)/O(n)
        @Override
        public boolean hasNext() {
            if (it == null) {
                return false;
            }
            return it.hasNext();
        }
    }

    class NestedInteger {
        Integer val;
        List<NestedInteger> list;

        public NestedInteger(Integer val) {
            this.val = val;
        }

        public NestedInteger(List<NestedInteger> list) {
            this.list = list;
        }

        // 如果其中存的是一个整数，则返回 true，否则返回 false
        public boolean isInteger() {
            return this.val != null;
        }

        // 如果其中存的是一个整数，则返回这个整数，否则返回 null
        public Integer getInteger() {
            return this.val;
        }

        // 如果其中存的是一个列表，则返回这个列表，否则返回 null
        public List<NestedInteger> getList() {
            return this.list;
        }
    }

    /**
     * 677. 键值映射
     * https://leetcode.cn/problems/map-sum-pairs/
     * 方法：前缀树TrieMap
     */
    // insert操作时间复杂度：O(n)，n是插入的字符串 key 的长度;sum操作的时间复杂度O(n)，n为给定的查询字符的长度，需要在前缀树中搜索给定的前缀
    // 空间复杂度O(cnm)，m表示key-val键值数，n为字符串key的最大长度
    static class MapSum {

        public MapSum() {

        }

        TrieMap7<Integer> trieMap = new TrieMap7<>();

        public void insert(String key, int val) {
            trieMap.put(key, val);
        }

        public int sum(String prefix) {
            List<String> pathList = trieMap.keysWithPrefix(prefix);
            if (pathList == null || pathList.size() == 0) {
                return 0;
            }
            int sum = 0;
            for (String path : pathList) {
                Integer val = trieMap.get(path);
                sum += val;
            }
            return sum;
        }
    }

    static class TrieMap7<V> {

        private static final int R = 26;

        class TrieNode<V> {
            TrieNode<V>[] children = new TrieNode[R];
            V val = null;
        }

        TrieNode<V> root;

        // 添加
        public void put(String key, V val) {
            root = put(root, key, val, 0);
        }

        private TrieNode<V> put(TrieNode<V> node, String key, V val, int i) {
            if (node == null) {
                node = new TrieNode<>();
            }
            if (key.length() == i) {
                node.val = val;
                return node;
            }
            char c = key.charAt(i);
            int index = c - 'a';
            node.children[index] = put(node.children[index], key, val, i + 1);
            return node;
        }

        // 查询所有包含前缀prefix的key的路径集合
        public List<String> keysWithPrefix(String prefix) {
            TrieNode<V> node = getNode(prefix);
            List<String> res = new ArrayList<>();
            if (node == null) {
                return res;
            }
            traverse(res, new StringBuilder(prefix), node);
            return res;
        }

        private void traverse(List<String> res, StringBuilder path, TrieNode<V> node) {
            if (node == null) {
                return;
            }
            if (node.val != null) {
                res.add(path.toString());
            }
            for (char c = 'a'; c <= 'z'; c++) {
                path.append(c);
                int index = c - 'a';
                traverse(res, path, node.children[index]);
                path.deleteCharAt(path.length() - 1);
            }
        }

        public V get(String key) {
            TrieNode<V> node = getNode(key);
            return node == null ? null : node.val;
        }

        private TrieNode<V> getNode(String key) {
            TrieNode<V> p = root;
            for (int i = 0; i < key.length(); i++) {
                if (p == null) {
                    return null;
                }
                char c = key.charAt(i);
                int index = c - 'a';
                p = p.children[index];
            }
            return p;
        }
    }

    /**
     * 1804. 实现 Trie （前缀树） II(付费题)
     * https://leetcode.cn/problems/implement-trie-ii-prefix-tree/
     * 方法：前缀树（(数组+V）
     * 思路：这题就可以用到TrieMap，每个插入的word就是键，插入的次数就是对应的值，然后复用TrieMap的 API 就能实现题目要求
     */
    class Trie6 {
        TrieMap6<Integer> trieMap = new TrieMap6<>();

        // 插入 word 并记录插入次数
        public void insert(String word) {
            Integer val = trieMap.get(word);
            if (val == null) {
                trieMap.put(word, 1);
            } else {
                trieMap.put(word, trieMap.get(word) + 1);
            }
        }

        // 查询 word 插入的次数
        public int countWordsEqualTo(String word) {
            Integer val = trieMap.get(word);
            return val == null ? 0 : val;
        }

        // 累加前缀为 prefix 的键的插入次数总和：先查询包含prefix的全部的key
        public int countWordsStartingWith(String prefix) {
            int res = 0;
            for (String key : trieMap.keysWithPrefix(prefix)) {
                res += trieMap.get(key);
            }
            return res;
        }

        // word 的插入次数减一：取出word键对应的值，这里需要注意判断，如果值减到0，需要将k-v移出，否则需要对值进行减1操作
        public void erase(String word) {
            int val = trieMap.get(word);
            if (val - 1 == 0) {
                trieMap.remove(word);
            } else {
                trieMap.put(word, val - 1);
            }
        }
    }

    class TrieMap6<V> {
        TrieMap6[] children;
        V val;

        public TrieMap6() {
            children = new TrieMap6[26];
            val = null;
        }

        // 插入 word 并记录插入次数
        public void put(String key, V v) {
            TrieMap6<V> root = this;
            put(key, root, v, 0);
        }

        private TrieMap6<V> put(String key, TrieMap6<V> node, V val, int i) {
            if (node == null) {
                node = new TrieMap6<>();
            }
            if (i == key.length()) {
                node.val = val;
                return node;
            }
            char c = key.charAt(i);
            node.children[c] = put(key, node.children[c], val, i + 1);
            return node;
        }

        // 查询 word 插入的次数
        public V get(String key) {
            TrieMap6<V> node = getNode(key);
            return node == null ? null : node.val;
        }

        private TrieMap6<V> getNode(String key) {
            TrieMap6<V> p = this;
            for (int i = 0; i < key.length(); i++) {
                if (p == null) {
                    return null;
                }
                char c = key.charAt(i);
                p = p.children[c];
            }
            return p;
        }

        // 将包含前缀prefix的key全部查出
        public List<String> keysWithPrefix(String prefix) {
            List<String> res = new ArrayList<>();
            TrieMap6<V> node = getNode(prefix);
            if (node == null) {
                return res;
            }
            traverse(res, node, new StringBuilder(prefix));
            return res;
        }

        private void traverse(List<String> res, TrieMap6<V> node, StringBuilder sbr) {
            if (node == null) {
                return;
            }
            if (node.val != null) {
                res.add(sbr.toString());
            }
            for (char c = 0; c < 26; c++) {
                sbr.append(c);
                traverse(res, node.children[c], sbr);
                sbr.deleteCharAt(c);
            }
        }

        // 删除key
        public void remove(String key) {
            remove(key, this, 0);
        }

        private TrieMap6<V> remove(String key, TrieMap6<V> node, int i) {
            if (node == null) {
                return null;
            }
            if (key.length() == i) {
                node.val = null;
            } else {
                char c = key.charAt(i);
                node.children[c] = remove(key, node.children[c], i + 1);
            }
            if (node.val != null) {
                return node;
            }
            // 只有有一个后缀分支就不能被删除
            for (char c = 0; c < 26; c++) {
                if (node.children[c] != null) {
                    return node;
                }
            }
            // 既没有存储 val，也没有后缀树枝，则该节点需要被清理
            return null;
        }
    }

    /**
     * 211. 添加与搜索单词 - 数据结构设计
     * https://leetcode.cn/problems/design-add-and-search-words-data-structure/
     * 方法2：前缀树(数组+isEnd) 【推荐】
     * 思路：考点就在于这个search函数进行通配符匹配，其实就是我们给TrieSet实现的hasKeyWithPattern方法，一个通配符.对应所有定义的英文字母
     */

    private static class WordDictionary2 {
        Trie5 trie = new Trie5();

        public WordDictionary2() {

        }

        // 时间复杂度：O(∣S∣)：∣S∣ 是每次添加或搜索的单词的长度
        // 空间复杂度：O(∣T∣⋅∣Σ∣):|T| 是所有添加的单词的长度之和，Σ 是字符集[26个]
        public void addWord(String word) {
            trie.add(word);
        }

        public boolean search(String word) {
            return trie.hasKeyWithPattern(word);
        }
    }


    private static class Trie5 {
        Trie5[] children;
        boolean isEnd;

        public Trie5() {
            children = new Trie5[26];
            isEnd = false;
        }

        public void add(String key) {
            Trie5 p = this;
            for (int i = 0; i < key.length(); i++) {
                char c = key.charAt(i);
                int index = c - 'a';
                if (p.children[index] == null) {
                    p.children[index] = new Trie5();
                }
                p = p.children[index];
            }
            p.isEnd = true;
        }

        public boolean hasKeyWithPattern(String key) {
            return hasKeyWithPattern(this, key, 0);

        }

        private boolean hasKeyWithPattern(Trie5 trie, String key, int i) {
            if (trie == null) {
                return false;
            }
            if (key.length() == i) {
                return trie.isEnd;
            }
            char c = key.charAt(i);
            // 如果是通配符.
            if ('.' == c) {
                for (int k = 0; k < 26; k++) {
                    if (hasKeyWithPattern(trie.children[k], key, i + 1)) {
                        return true;
                    }
                }
            } else {
                int index = c - 'a';
                return hasKeyWithPattern(trie.children[index], key, i + 1);
            }
            return false;
        }
    }

    /**
     * 211. 添加与搜索单词 - 数据结构设计
     * https://leetcode.cn/problems/design-add-and-search-words-data-structure/
     * 方法1：前缀树(Map实现) 【效率低不推荐】
     * 思路：考点就在于这个search函数进行通配符匹配，其实就是我们给TrieSet实现的hasKeyWithPattern方法，一个通配符.对应所有定义的英文字母
     * 这里有1个误区：题目的第一行是说要执行的步骤，不是输入的值【大坑】
     */

    private static class WordDictionary {
        Trie4 trie = new Trie4();

        public WordDictionary() {

        }

        // 时间复杂度：O(∣S∣)：∣S∣ 是每次添加或搜索的单词的长度
        // 空间复杂度：O(∣T∣⋅∣Σ∣):|T| 是所有添加的单词的长度之和，Σ 是字符集[16个]
        public void addWord(String word) {
            trie.add(word);
        }

        public boolean search(String word) {
            return trie.hasKeyWithPattern(word);
        }
    }

    private static class Trie4 {
        private Map<Character, Trie4> children;

        public Trie4() {
            children = new HashMap<>();
        }

        /**
         * 添加key
         *
         * @param key
         */
        // O(n)/O(n)
        public void add(String key) {
            Trie4 p = this;
            for (int i = 0; i < key.length(); i++) {
                if (p.children == null) {
                    p.children = new HashMap<>();
                }
                char c = key.charAt(i);
                p.children.putIfAbsent(c, new Trie4());
                // 少了一步
                p = p.children.get(c);
            }
            // 结束符
            p.children.put('#', new Trie4());
        }

        /**
         * 是否包含通配符的pattern
         *
         * @param pattern
         * @return
         */
        // O(n)/O(n)
        public boolean hasKeyWithPattern(String pattern) {
            return hasKeyWithPattern(this, pattern, 0);
        }

        private boolean hasKeyWithPattern(Trie4 node, String pattern, int index) {
            if (node == null) {
                return false;
            }
            // 到达查找字符串结尾，看有没有字符串存储，即判断#有没有。
            if (pattern.length() == index) {
                if (node.children != null) {
                    return node.children.containsKey('#');
                }
                return false;
            }
            char c = pattern.charAt(index);
            // 遇到通配符
            if ('.' == c) {
                // A~Z的ASCII码值从65~90 a~z的ASCII码值从97~122
                for (char ch = 'a'; ch <= 'z'; ch++) {
                    if (hasKeyWithPattern(node.children.get(ch), pattern, index + 1)) {
                        return true;
                    }
                }
            }
            // 没有遇到通配符
            return hasKeyWithPattern(node.children.get(c), pattern, index + 1);
        }
    }

    /**
     * 648. 单词替换
     * https://leetcode.cn/problems/replace-words/
     * 方法2：前缀树内部使用Map<Character,Trie3>
     * 思路：此题考察的是最短前缀问题，参考shortPrefixOf函数
     * 优化：因为可以提前预置前缀，如果提前设定好一个字符的存储的空间大小，也就是说children是固定大小256，也就是很浪费空间的了，
     * 换成Map存储提前预置的前缀值【树枝+末节点】，可以节省空间
     *
     * @param dictionary
     * @param sentence
     * @return
     */
    // O(d+s)/O(d+s)
    // 其中d 是dictionary 的字符数，s 是sentence 的字符数。构建字典树消耗 O(d)时间，每个单词搜索前缀均消耗线性时间。
    //   构建哈希集合消耗 O(d) 空间，分割 sentence 消耗 O(s)空间
    public String replaceWords2(List<String> dictionary, String sentence) {
        Trie3 trie = new Trie3();
        for (String key : dictionary) {
            trie.add(key);
        }

        StringBuilder sb = new StringBuilder();
        String[] words = sentence.split(" ");
        // 处理句子中的单词
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            // 在 Trie 树中搜索最短词根（最短前缀）
            String prefix = trie.shortestPrefixOf(word);
            if (prefix != null) {
                // 如果搜索到了，改写为词根
                sb.append(prefix);
            } else {
                // 否则，原样放回
                sb.append(word);
            }
            if (i != words.length - 1) {
                // 添加单词之间的空格
                sb.append(" ");
            }
        }
        return sb.toString();
    }

    private class Trie3 {
        private Map<Character, Trie3> children;

        public Trie3() {
            children = new HashMap<>();
        }

        // 添加字符串
        public void add(String key) {
            // 当前节点
            Trie3 p = this;
            for (int i = 0; i < key.length(); i++) {
                char c = key.charAt(i);
                if (null == p.children) {
                    // 创建分支
                    p.children = new HashMap<>();
                }
                // 给树枝和节点赋值
                p.children.putIfAbsent(c, new Trie3());
                p = p.children.get(c);
            }
            // 加完前缀使用一个结束符#完成
            p.children.put('#', new Trie3());
        }

        // 获取最短前缀
        public String shortestPrefixOf(String key) {
            Trie3 p = this;
            for (int i = 0; i < key.length(); i++) {
                if (p == null) {
                    return null;
                }
                if (p.children.containsKey('#')) {
                    return key.substring(0, i);
                }
                char c = key.charAt(i);
                p = p.children.get(c);
            }
            // 重要的一步，需要检查本省key就是一个前缀的情况。因为循环遍历的是树枝，最后一个树枝遍历完，赋值给p后，就不进循环了，所以在此需要单独校验一下
            if (p != null && p.children.containsKey('#')) {
                return key;
            }
            return null;
        }
    }

    /**
     * 648. 单词替换
     * https://leetcode.cn/problems/replace-words/
     * 方法1：前缀树内部使用固定256大小数组+结束标签
     * 思路：此题考察的是最短前缀问题，参考shortPrefixOf函数
     * 把输入的词根列表dict存入TrieSet，然后直接复用我们实现的shortestPrefixOf函数就行
     *
     * @param dictionary
     * @param sentence
     * @return
     */
    public String replaceWords(List<String> dictionary, String sentence) {
        Trie2 trie = new Trie2();
        for (String key : dictionary) {
            trie.add(key);
        }

        StringBuilder sb = new StringBuilder();
        String[] words = sentence.split(" ");
        // 处理句子中的单词
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            // 在 Trie 树中搜索最短词根（最短前缀）
            String prefix = trie.shortestPrefixOf(word);
            if (prefix != null) {
                // 如果搜索到了，改写为词根
                sb.append(prefix);
            } else {
                // 否则，原样放回
                sb.append(word);
            }
            if (i != words.length - 1) {
                // 添加单词之间的空格
                sb.append(" ");
            }
        }
        return sb.toString();
    }

    private class Trie2 {
        private Trie2[] children;
        private boolean isEnd;

        public Trie2() {
            children = new Trie2[256];
            isEnd = false;
        }

        // 添加字符串
        public void add(String key) {
            // 当前节点
            Trie2 p = this;
            for (int i = 0; i < key.length(); i++) {
                char c = key.charAt(i);
                if (null == p.children[c]) {
                    // 创建分支
                    p.children[c] = new Trie2();
                }
                p = p.children[c];
            }
            p.isEnd = true;
        }

        // 获取最短前缀
        public String shortestPrefixOf(String key) {
            Trie2 p = this;
            for (int i = 0; i < key.length(); i++) {
                if (p == null) {
                    return null;
                }
                if (p.isEnd) {
                    return key.substring(0, i);
                }
                char c = key.charAt(i);
                p = p.children[c];
            }
            // 重要的一步，需要检查本省key就是一个前缀的情况。因为循环遍历的是树枝，最后一个树枝遍历完，赋值给p后，就不进循环了，所以在此需要单独校验一下
            if (p != null && p.isEnd) {
                return key;
            }
            return null;
        }
    }


    /**
     * 208. 实现 Trie (前缀树)
     * https://leetcode.cn/problems/implement-trie-prefix-tree/
     * 思路：题目让我们实现的几个函数其实就是TrieSet的部分 API，所以直接封装一个TrieSet就能解决这道题了，该题不需要存储val值，所以使用boolean表示是不是
     * 存有字符串
     */
    // 初始化为 O(1)，其余操作为 O(|S|)，其中 |S|是每次插入或查询的字符串的长度。
    // O(∣T∣⋅Σ)，其中 |T|为所有插入字符串的长度之和，Σ 为字符集的大小，本题 Σ=26。
    private class Trie {

        private Trie[] children;
        private boolean isEnd;

        public Trie() {
            children = new Trie[26];
            isEnd = false;
        }


        // 使用迭代
        public void insert(String word) {
            Trie node = this;
            for (int i = 0; i < word.length(); i++) {
                int index = word.charAt(i) - 'a';
                if (null == node.children[index]) {
                    node.children[index] = new Trie();
                }
                node = node.children[index];
            }
            node.isEnd = true;
        }

        public boolean search(String word) {
            Trie node = searchPrefix(word);
            return node != null && node.isEnd;
        }

        public boolean startsWith(String prefix) {
            return searchPrefix(prefix) != null;
        }

        private Trie searchPrefix(String prefix) {
            Trie node = this;
            for (int i = 0; i < prefix.length(); i++) {
                int index = prefix.charAt(i) - 'a';
                // 只要存在空就不存在了，直接返回
                if (null == node.children[index]) {
                    return null;
                }
                node = node.children[index];
            }
            return node;
        }
    }

    /**
     * 95. 不同的二叉搜索树 II
     * https://leetcode.cn/problems/unique-binary-search-trees-ii/
     * 方法：递归+备忘录
     * 思路：
     * 1、穷举root节点的所有可能。
     * 2、递归构造出左右子树的所有合法 BST。
     * 3、给root节点穷举所有左右子树的组合。
     *
     * @param n
     * @return
     */
    // O(4^n/n^(1/2))/O(4^n/n^(1/2))
    // 生成一棵二叉搜索树需要 O(n)O(n) 的时间复杂度，一共有Gn棵二叉搜索树，也就是 O(nGn)而卡特兰数以4^n/n^(3/2)增长，因此总的时间复杂度为O(4^n/n^(1/2))
    // n个点生成的二叉搜索树有 Gn 棵，每棵有n个节点，因此存储空间需要O(nGn)
    List<TreeNode>[][] memo2;

    public List<TreeNode> generateTrees(int n) {
        if (n == 0) {
            return new ArrayList<>();
        }
        memo2 = new List[n + 1][n + 1];
        // 构造闭区间 [1, n] 组成的 BST
        return buildBst(1, n);
    }

    // 构造闭区间 [lo, hi] 组成的BST
    private List<TreeNode> buildBst(int low, int high) {
        List<TreeNode> resBst = new ArrayList<>();
        // 保证左子节点小于右子节点，这里包含了相等的情况，这里一定要注，不要写等于号，因为没有值的节点是需要返回null的
        if (low > high) {
            resBst.add(null);
            return resBst;
        }
        if (memo2[low][high] != null) {
            return memo2[low][high];
        }
        // 1、穷举 root 节点的所有可能。
        for (int mid = low; mid <= high; mid++) {
            // 2、递归构造出左右子树的所有合法 BST。
            List<TreeNode> leftTree = buildBst(low, mid - 1);
            List<TreeNode> rightTree = buildBst(mid + 1, high);
            // 3、给 root 节点穷举所有左右子树的组合。
            for (TreeNode left : leftTree) {
                for (TreeNode right : rightTree) {
                    // mid 作为根节点 root 的值
                    TreeNode root = new TreeNode(mid);
                    root.left = left;
                    root.right = right;
                    resBst.add(root);
                    memo2[low][high] = resBst;
                }
            }
        }
        return resBst;
    }

    /**
     * 96. 不同的二叉搜索树
     * https://leetcode.cn/problems/unique-binary-search-trees/
     * 方法：递归+备忘录
     * 思路：首先给的是n，也就是计算的是闭区间[1,n]的所有数字组成的BST的个数，左子树的组合数和右子树的组合数乘积就是i作为根节点时的BST个数。
     * 遍历区间[low,high]区间，mid作为根节点的，当low>high则，返回1。为防止重复计算，使用备忘录
     *
     * @param n
     * @return
     */
    // 备忘录
    int[][] memo;

    // O(n)/O(n)
    public int numTrees(int n) {
        // 备忘录的值初始化为 0
        memo = new int[n + 1][n + 1];
        // 计算闭区间 [1, n] 组成的 BST 个数
        return count(1, n);
    }

    // 计算闭区间 [lo, hi] 组成的 BST 个数
    private int count(int low, int high) {
        if (low >= high) {
            return 1;
        }
        // 查备忘录
        if (memo[low][high] != 0) {
            return memo[low][high];
        }
        int res = 0;
        for (int mid = low; mid <= high; mid++) {
            // mid的值作为根节点 root
            int left = count(low, mid - 1);
            int right = count(mid + 1, high);
            // 左右子树的组合数乘积是 BST 的总数
            res += left * right;
        }
        // 将结果存入备忘录
        memo[low][high] = res;
        return res;
    }


    /**
     * 450. 删除二叉搜索树中的节点
     * https://leetcode.cn/problems/delete-node-in-a-bst/
     * 方法：迭代
     * 思路：1、需要维护两个节点，cur和curParent。找到值等于key的节点cur和其父节点curParent。
     * 2、删除cur，实际上是找到cur左子树的max或者右子树的min节点进行替换。然后删除掉这个max或者min。
     * 删除考虑3种情况：cur没有子节点；cur有一个子节点；cur有两个子节点。
     * 情况1、2好处理，直接将要删除节点的下一个节点覆盖当前节点就可以了；
     * 情况3比较复杂，为了不破坏 BST 的性质，被删除节点必须找到其左子树中最大的那个节点，或者其右子树中最小的那个节点来接替自己。
     * 此处使用第二种来解答。
     */
    // O(n)/O(1)
    public TreeNode deleteNode2(TreeNode root, int key) {
        // 1. 找到key的节点
        TreeNode cur = root, curParent = null;
        while (cur != null && cur.val != key) {
            curParent = cur;
            // 不是在左边就是在右边
            if (cur.val > key) {
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        }
        // 没有这个值为key的节点cur
        if (cur == null) {
            return root;
        }
        // 2. 删除cur(三种情况)
        if (cur.left == null && cur.right == null) {
            cur = null;
        } else if (cur.left == null) {
            cur = cur.right;
        } else if (cur.right == null) {
            cur = cur.left;
        } else {
            // 寻找右子树的最小子节点
            TreeNode min = cur.right;
            TreeNode minParent = cur;
            while (min.left != null) {
                minParent = min;
                min = min.left;
            }
            // 维护minParent
            if (minParent.val == cur.val) {// cur的右子树没有左子节点
                minParent.right = min.right;
            } else {
                minParent.left = min.right;
            }
            // 替换cur
            min.left = cur.left;
            min.right = cur.right;
            cur = min;
        }
        // 维护curParent
        if (curParent == null) {
            return cur;
        } else {
            if (curParent.left != null && curParent.left.val == key) {
                curParent.left = cur;
            } else {
                curParent.right = cur;
            }
        }
        return root;
    }


    /**
     * 450. 删除二叉搜索树中的节点
     * https://leetcode.cn/problems/delete-node-in-a-bst/
     * 方法：递归
     * 思路：删除考虑3种情况。情况1、2好处理，直接将要删除节点的下一个节点覆盖当前节点就可以了；
     * 情况3比较复杂，为了不破坏 BST 的性质，被删除节点必须找到其左子树中最大的那个节点，或者其右子树中最小的那个节点来接替自己。
     * 此处使用第二种来解答。
     */
    // O(n)/O(n)，其中n为root的节点个数。最差情况下，寻找和删除minNode各需要遍历一次树/递归的深度最深为 O(n)
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return null;
        }
        // 处理情况3：删除节点有两个非空子节点
        if (root.val == key) {
            // 排除两种情况：情况1：恰好是末端节点，两个子节点都为空；情况2：只有一个非空子节点，那么它要让这个孩子接替自己的位置
            if (root.left == null) {
                return root.right;
            }
            if (root.right == null) {
                return root.left;
            }
            // 找到了要删除的节点，获取当前节点的右子树的最小值节点
            TreeNode minNode = getMin(root.right);
            // 删除掉最小值节点，返回右子树
            root.right = deleteNode(root.right, minNode.val);
            // 用右子树最小的节点替换 root 节点
            minNode.left = root.left;
            minNode.right = root.right;
            root = minNode;
        } else if (root.val > key) {
            root.left = deleteNode(root.left, key);
        } else if (root.val < key) {
            root.right = deleteNode(root.right, key);
        }
        return root;
    }

    // 获取BST的右子树的最小值
    private TreeNode getMin(TreeNode root) {
        // BST 最左边的就是最小的
        while (root.left != null) {
            root = root.left;
        }
        return root;
    }

    /**
     * 701. 二叉搜索树中的插入操作
     * https://leetcode.cn/problems/insert-into-a-binary-search-tree/
     * 方法：迭代
     * 思路：利用BST性质：左子树全部节点值要小于当前节点值，右子树的节点值全部大于当前节点值。
     * 根据val与root.val的大小关系，就可以确定要将val插入到哪个子树中。如果该子树不为空，则问题转化成了
     * 将val插入到对应子树上。否则，在此处新建一个以val为值的节点，并链接到其父节点root上。
     *
     * @param root
     * @param val
     * @return
     */
    // O(n)/O(1)
    public TreeNode insertIntoBST2(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        TreeNode pos = root;
        while (pos != null) {
            if (pos.val > val) {
                if (pos.left == null) {
                    pos.left = new TreeNode(val);
                    break;
                }
                pos = pos.left;
            } else {
                if (pos.right == null) {
                    pos.right = new TreeNode(val);
                    break;
                }
                pos = pos.right;
            }
        }
        return root;
    }

    /**
     * 701. 二叉搜索树中的插入操作
     * https://leetcode.cn/problems/insert-into-a-binary-search-tree/
     * 方法：递归
     * 思路：利用BST性质：左子树全部节点值要小于当前节点值，右子树的节点值全部大于当前节点值。
     * 类似二叉树的构造问题，函数要返回 TreeNode 类型，并且要对递归调用的返回值进行接收。
     *
     * @param root
     * @param val
     * @return
     */
    // O(n)/O(n)
    public TreeNode insertIntoBST(TreeNode root, int val) {
        // 找到空位置插入新节点
        if (root == null) {
            return new TreeNode(val);
        }
        // if (root.val == val)
        // BST 中一般不会插入已存在元素
        if (root.val > val) {
            root.left = insertIntoBST(root.left, val);
        } else if (root.val < val) {
            root.right = insertIntoBST(root.right, val);
        }
        return root;
    }

    /**
     * 98. 验证二叉搜索树
     * https://leetcode.cn/problems/validate-binary-search-tree/
     * 方法：递归
     * 思路：利用BST性质：左子树全部节点值要小于当前节点值，右子树的节点值全部大于当前节点值。
     * 递归判断当前节点的大于左子树的最max，小于右子树的min
     *
     * @param root
     * @return
     */
    // O(n)/O(n)
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, null, null);
    }

    /* 限定以 root 为根的子树节点必须满足 max.val > root.val > min.val */
    private boolean isValidBST(TreeNode root, TreeNode min, TreeNode max) {
        if (root == null) return true;
        // 若 root.val 不符合 max 和 min 的限制，说明不是合法 BST
        if (min != null && root.val <= min.val) return false;
        if (max != null && root.val >= max.val) return false;
        // 限定左子树的最大值是 root.val，右子树的最小值是 root.val
        return isValidBST(root.left, min, root) && isValidBST(root.right, root, max);
    }

    /**
     * 1038. 从二叉搜索树到更大和树
     * https://leetcode.cn/problems/binary-search-tree-to-greater-sum-tree/
     * 方法：反序中序遍历
     * 思路：利用BST中序遍历的特性，倒序打印节点值，当前节点之前的值（包括当前节点）做累加，更新当前节点值为累加和的值
     */
    // O(n)/O(n)
    public TreeNode bstToGst(TreeNode root) {
        traverse5(root);
        return root;
    }

    int sum2 = 0;

    private void traverse5(TreeNode root) {
        if (root == null) {
            return;
        }
        traverse5(root.right);
        sum2 += root.val;
        root.val = sum2;
        traverse5(root.left);
    }

    /**
     * 538. 把二叉搜索树转换为累加树
     * https://leetcode.cn/problems/convert-bst-to-greater-tree/
     * 方法：反序中序遍历
     * 思路：利用BST中序遍历的特性，倒序打印节点值，当前节点之前的值（包括当前节点）做累加，更新当前节点值为累加和的值
     */
    // O(n)/O(n)
    public TreeNode convertBST(TreeNode root) {
        traverse4(root);
        return root;
    }

    // 记录累加和
    int sum = 0;

    // 中序遍历，倒序，为的是累加比当前节点大的节点值的和
    private void traverse4(TreeNode root) {
        if (root == null) {
            return;
        }
        traverse4(root.right);
        sum += root.val;
        root.val = sum;
        traverse4(root.left);
    }

    /**
     * 230. 二叉搜索树中第K小的元素
     * https://leetcode.cn/problems/kth-smallest-element-in-a-bst/
     * 方法：利用BST的中序遍历为升序的特性
     *
     * @param root
     * @param k
     * @return
     */
    // O(n)/O(n)
    // 记录结果
    int result = 0;

    public int kthSmallest(TreeNode root, int k) {
        // 利用 BST 的中序遍历特性
        traverse(root, k);
        return result;
    }

    // 记录当前元素的排名
    int rank = 0;

    private void traverse(TreeNode root, int k) {
        if (root == null) {
            return;
        }
        traverse(root.left, k);
        // 中序遍历代码位置
        rank++;
        if (rank == k) {
            // 找到第K个最小的元素
            result = root.val;
            return;
        }
        traverse(root.right, k);
    }

    /**
     * 652. 寻找重复的子树
     * https://leetcode.cn/problems/find-duplicate-subtrees/
     * 方法：分解法+利用后续位置+分配节点编号
     * 思路：假设每棵子树都有一个唯一标识符：只有当两个子树的id相同时，认为这两个子树是相同的。一个节点node的左孩子id为x，
     * 右孩子id为y，那么该节点的id为(node.val, x, y)
     *
     * @param root
     * @return
     */
    // 记录重复的子树根节点
    List<TreeNode> res2;
    // 标识符计数器
    int biz;
    // 记录所有三元组(node.val, x, y)以及其标识符uid
    HashMap<String, Integer> partTreeMap;
    // 记录标识符uid出现的次数
    HashMap<Integer, Integer> uidCountMap;

    // O(n)/O(n) 时间复杂度：N是二叉树上节点的数量，每个节点访问一次。
    // 空间复杂度：每棵子树的存储空间都为O(1)
    /* 主函数 */
    public List<TreeNode> findDuplicateSubtrees2(TreeNode root) {
        biz = 1;// 不可以为0，测试案例是[0,0,0,0,null,null,0,null,null,null,0]
        res2 = new ArrayList<>();
        partTreeMap = new HashMap<>();
        uidCountMap = new HashMap<>();
        traverse3(root);
        return res2;
    }

    private int traverse3(TreeNode root) {
        // uid为0的情况是root为null情况，所以biz不能初始化值为0
        if (root == null) {
            return 0;
        }
        int leftUid = traverse3(root.left);
        int rightUid = traverse3(root.right);
        // 后序位置
        String strTree = root.val + "," + leftUid + "," + rightUid;
        Integer uid = partTreeMap.computeIfAbsent(strTree, x -> biz++);
        Integer existNum = uidCountMap.getOrDefault(uid, 0);
        // 给uid的出现次数加一
        uidCountMap.put(uid, existNum + 1);
        if (uidCountMap.get(uid) == 2) {
            res2.add(root);
        }
        return uid;
    }


    /**
     * 652. 寻找重复的子树
     * https://leetcode.cn/problems/find-duplicate-subtrees/
     * 方法：分解法+利用后续位置+序列化
     * 思路：遍历树，将数进行序列化为字符串，在后序位置每次将左右根节点转为字符串，存入一个map(key:这个字符串;value:字符串出现次数)。
     * 将出现重复的字符串存入到一个结果集合中
     *
     * @param root
     * @return
     */
    // 记录重复的子树根节点
    List<TreeNode> res;
    // 记录所有子树以及出现的次数
    HashMap<String, Integer> strMap;

    // O(n^2)/O(n^2) 时间复杂度：N是二叉树上节点的数量。遍历所有节点，在每个节点处序列化需要时间 O(N)。假设 root.val
    // 的长度为 a，root.left 的长度为 b，root.right 的长度为 c，每次字符串拼接所需时间是 a + b + c <= N，而一共有 N 个节点，所以是 O(N^2)
    // 空间复杂度：count的大小
    /* 主函数 */
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        res = new ArrayList<>();
        strMap = new HashMap<>();
        traverse2(root);
        return res;
    }

    /* 辅助函数 */
    private String traverse2(TreeNode root) {
        if (root == null) {
            return "null";
        }
        String leftStr = traverse2(root.left);
        String rightStr = traverse2(root.right);
        String strTree = leftStr + "," + rightStr + "," + root.val;
        int existNum = strMap.getOrDefault(strTree, 0);
        // 多次重复也只会被加入结果集一次
        if (existNum == 1) {
            res.add(root);
        }
        // 给子树对应的出现次数加一
        strMap.put(strTree, existNum + 1);
        return strTree;
    }

    /**
     * 889. 根据前序和后序遍历构造二叉树
     * https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-postorder-traversal/
     * 方法：分解法
     * 思路：先根据前序遍历结果第二个元素找到左子树节点，再去后续遍历结果中找到左子树节点位置，计算出左子树的节点数，
     * 进而定位出左右子树在preorder、postorder中的位置
     *
     * @param preorder
     * @param postorder
     * @return
     */
    // 存储 postorder 中值到索引的映射
    Map<Integer, Integer> valToIndex3 = new HashMap<>();

    // O(n)/O(n)
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        for (int i = 0; i < postorder.length; i++) {
            valToIndex3.put(postorder[i], i);
        }
        return build3(preorder, 0, preorder.length - 1,
                postorder, 0, postorder.length - 1);
    }

    // 定义：根据 preorder[preStart..preEnd] 和 postorder[postStart..postEnd]
    // 构建二叉树，并返回根节点
    private TreeNode build3(int[] preorder, int preStart, int preEnd,
                            int[] postorder, int postStart, int postEnd) {
        if (preStart > preEnd) {
            return null;
        }
        // 注意这里，不处理，取leftVal会有问题
        if (preStart == preEnd) {
            return new TreeNode(preorder[preStart]);
        }
        // root.left 的值是前序遍历第二个元素
        // 通过前序和后序遍历构造二叉树的关键在于通过左子树的根节点
        // 确定 preorder 和 postorder 中左右子树的元素区间
        int leftVal = preorder[preStart + 1];
        // leftRootVal 在后序遍历数组中的索引
        int index = valToIndex3.get(leftVal);
        // 左子树的元素个数
        int leftSize = index - postStart + 1;
        // root 节点对应的值就是前序遍历数组的第一个元素
        int rootVal = preorder[preStart];
        // 先构造出当前根节点
        TreeNode root = new TreeNode(rootVal);
        // 递归构造左右子树
        // 根据左子树的根节点索引和元素个数推导左右子树的索引边界
        TreeNode left = build3(preorder, preStart + 1, preStart + leftSize,
                postorder, postStart, index);
        TreeNode right = build3(preorder, preStart + leftSize + 1, preEnd,
                postorder, index + 1, postEnd);
        root.left = left;
        root.right = right;
        return root;
    }

    /**
     * 106.从中序与后序遍历序列构造二叉树
     * https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
     * 方法：分解法
     * 思路：先明确，构造二叉树，先要找到根节点，然后构建左右子树。根节点->inorder左右子树边界->左子树个数->preorder左右子树边界
     * 首先找到先序遍历数组的第一个元素，即为根节点，根据题意，二叉树的节点值没有重复元素，所以为了提升效率，遍历中序遍历数组的时候
     * 提前将中序遍历的元素以及索引值存入一个map集合中。以inorder为目标，定位到根节点的索引值，该值左(右)侧为左(右)子树节点。然后定位
     * postorder，根据左子树节点数【根据inorder根节点左侧节点数】定位左右子树的分隔处，最终构建出左右子树。
     * 与前、中序构建不同点，根节点在postorder最后一个元素
     *
     * @param inorder
     * @param postorder
     * @return
     */
    // 存储 inorder 中值到索引的映射
    Map<Integer, Integer> valToIndex2 = new HashMap<>();

    // O(n)/O(n)
    public TreeNode buildTree2(int[] inorder, int[] postorder) {
        for (int i = 0; i < inorder.length; i++) {
            valToIndex2.put(inorder[i], i);
        }
        return build2(inorder, 0, inorder.length - 1,
                postorder, 0, postorder.length - 1);
    }

    /*
    build 函数的定义：
    后序遍历数组为 postorder[postStart..postEnd]，
    中序遍历数组为 inorder[inStart..inEnd]，
    构造二叉树，返回该二叉树的根节点
    */
    private TreeNode build2(int[] inorder, int inStart, int inEnd,
                            int[] postorder, int postStart, int postEnd) {
        if (inStart > inEnd) {
            return null;
        }
        // root 节点对应的值就是后序遍历数组的最后一个元素
        int rootVal = postorder[postEnd];
        // rootVal 在中序遍历数组中的索引
        int index = valToIndex2.get(rootVal);
        // 左子树的节点个数
        int leftSize = index - inStart;
        // 递归构造左右子树【注意，后序去除根节点】
        TreeNode left = build2(inorder, inStart, index - 1,
                postorder, postStart, postStart + leftSize - 1);
        TreeNode right = build2(inorder, index + 1, inEnd,
                postorder, postStart + leftSize, postEnd - 1);
        TreeNode root = new TreeNode(rootVal);
        root.left = left;
        root.right = right;
        return root;
    }

    /**
     * 105. 从前序与中序遍历序列构造二叉树
     * https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
     * 方法：分解法
     * 思路：先明确，构造二叉树，先要找到根节点，然后构建左右子树。根节点->inorder左右子树边界->左子树个数->preorder左右子树边界
     * 首先找到先序遍历数组的第一个元素，即为根节点，根据题意，二叉树的节点值没有重复元素，所以为了提升效率，遍历中序遍历数组的时候
     * 提前将中序遍历的元素以及索引值存入一个map集合中。以inorder为目标，定位到根节点的索引值，该值左(右)侧为左(右)子树节点。然后定位
     * preorder，根据左子树节点数【根据inorder根节点左侧节点数】定位左右子树的分隔处，最终构建出左右子树。
     *
     * @param preorder
     * @param inorder
     * @return
     */
    Map<Integer, Integer> valToIndex = new HashMap<>();

    // O(n)/O(n)
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 存储中序遍历数组的值和索引
        for (int i = 0; i < inorder.length; i++) {
            valToIndex.put(inorder[i], i);
        }
        return build(preorder, 0, preorder.length - 1,
                inorder, 0, inorder.length - 1);
    }

    private TreeNode build(int[] preorder, int preStart, int preEnd,
                           int[] inorder, int inStart, int inEnd) {
        if (preStart > preEnd) {
            return null;
        }
        // root 节点对应的值就是前序遍历数组的第一个元素
        int rootVal = preorder[preStart];
        // 去inorder中找左右子树分界位置:rootVal 在中序遍历数组中的索引
        int index = valToIndex.get(rootVal);
        // 左子树节点数
        int leftSize = index - inStart;
        // 先构造出当前根节点
        TreeNode root = new TreeNode(rootVal);
        // 递归构造左右子树
        TreeNode left = build(preorder, preStart + 1, preStart + leftSize,
                inorder, inStart, index - 1);
        TreeNode right = build(preorder, preStart + leftSize + 1, preEnd,
                inorder, index + 1, inEnd);
        root.left = left;
        root.right = right;
        return root;
    }


    /**
     * 654. 最大二叉树
     * https://leetcode.cn/problems/maximum-binary-tree/
     * 方法：分解法
     * 思路：寻找到nums中的最大值就是根节点，然后根据索引递归调用左右数组构造左右子树即可【最大值左右两侧分别对应的是
     * 左子树和右子树】。
     *
     * @param nums
     * @return
     */
    // O(n)/O(n)
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return build(nums, 0, nums.length - 1);
    }

    // 定义：将 nums[lo..hi] 构造成符合条件的树，返回根节点
    private TreeNode build(int[] nums, int low, int high) {
        if (low > high) {
            return null;
        }
        // 找到数组中的最大值和对应的索引
        int maxValue = Integer.MIN_VALUE;
        int index = -1;
        for (int i = low; i <= high; i++) {
            if (maxValue < nums[i]) {
                maxValue = nums[i];
                index = i;
            }
        }
        // 先构造出根节点
        TreeNode root = new TreeNode(maxValue);
        // 递归调用构造左右子树
        TreeNode left = build(nums, low, index - 1);
        TreeNode right = build(nums, index + 1, high);
        root.left = left;
        root.right = right;
        return root;
    }

    /**
     * 114. 二叉树展开为链表
     * https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/
     * 方法：分解法【由于本题目要求，无返回值，言外之意就是让我们直接对传入的节点直接改为链表，所以在此不能使用一次遍历解决】
     *
     * @param root
     */
    // O(n)/O(n)
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        // 利用定义，把左右子树拉平
        flatten(root.left);
        flatten(root.right);
        // 后序位置
        // 1、左右子树已经被拉平成一条链表
        TreeNode leftTree = root.left;
        TreeNode rightTree = root.right;
        // 2、将左子树作为右子树
        root.left = null;
        root.right = leftTree;
        // 3、将原先的右子树接到当前右子树的末端
        TreeNode p = root;
        while (p.right != null) {
            p = p.right;
        }
        p.right = rightTree;
    }

    /**
     * 116. 填充每个节点的下一个右侧节点指针
     * https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/
     * 方法2：层序遍历
     * 思路：将每一次层的节点加入到队列中，遍历每层队列中的元素，进行元素连接，同时将下层的节点加入队列中
     *
     * @param root
     * @return
     */
    // O(n)/O(n)
    public Node connect2(Node root) {
        if (root == null) {
            return null;
        }
        // 初始化队列同时将第一层节点加入队列中，即根节点
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        // 外层的 while 循环迭代的是层数
        while (!queue.isEmpty()) {
            // 记录当前队列大小
            int size = queue.size();
            // 遍历这一层的所有节点
            for (int i = 0; i < size; i++) {
                // 从队首取出元素
                Node node = queue.poll();
                // 连接
                if (i < size - 1) {
                    node.next = queue.peek();
                }
                // 拓展下一层节点
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        return root;
    }

    /**
     * 116. 填充每个节点的下一个右侧节点指针
     * https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/
     * 方法1：三叉树遍历(推荐)
     * 思路：一棵二叉树被抽象成了一棵三叉树，三叉树上的每个节点就是原先二叉树的两个相邻节点
     *
     * @param root
     * @return
     */
    // O(n)/O(n)
    public Node connect(Node root) {
        if (root == null) {
            return null;
        }
        // 遍历三叉树，连接相邻点
        traverse(root.left, root.right);
        return root;
    }

    // 三叉树遍历框架  把node1与node2想象成一个节点
    private void traverse(Node node1, Node node2) {
        if (node1 == null && node2 == null) {
            return;
        }
        // 前序位置
        // 将传入的两个节点穿起来
        node1.next = node2;
        // 连接相同父节点的两个子节点
        traverse(node1.left, node1.right);
        traverse(node2.left, node2.right);
        // 连接跨越父节点的两个子节点
        traverse(node1.right, node2.left);
    }
}
